79B - Colorful Field - CodeForces Solution

import math

numbers = list(map(int, input().split()))
rows    = numbers[0]
columns = numbers[1]
waste   = numbers[2]
queries = numbers[3]
fruite  = ['Carrots' , 'Kiwis' , 'Grapes']
indexs  = {}
arr     = []
for i in range ( 0 , waste) :
    x = list(map(int , input().split()))
    if not f'{x[0]}' in indexs :
        indexs[f'{x[0]}'] = len(arr)
        info = {
            'row' : x[0] ,
            'up'  : 0 ,
            'in'  : [x[1]]
        }
        arr.append(info)
    else :
        arr[indexs[f'{x[0]}']]['in'].append(x[1])
def re_row(key):
    return key['row']
arr.sort(key=re_row)
for i in range(0 , len(arr)):
    if i != 0 :
        arr[i]['up'] = arr[i-1]['up'] + len(arr[i - 1]['in'])
    indexs[f'{arr[i]["row"]}'] = i
def find_wast_rows(target , arr):
    start = 0
    end   = len(arr) - 1
    row    = 0
    while start <= end :
        middel = math.floor((start + end) / 2)
        if arr[middel]['row'] > target :
            if middel == 0 :
                row ='NONE'
                break
            if arr[middel - 1 ]['row'] < target:
                row = arr[middel - 1]['row']
                break
            else :
                end = middel - 1
        elif arr[middel]['row'] < target :
            if middel == len(arr) - 1 :
                row = arr[middel]['row']
                break
            if arr[middel + 1]['row'] > target :
                row = arr[middel]['row']
                break
            else :
                start = middel +1
        else :
            row = arr[middel]['row']
            break
    return row
def calc(wast_num , column_arr , row , column , columns_number):
    def the_num(row , columns_number , column , dif):
        x =  ( (row-1) * columns_number ) - dif
        y = column
        z = y + x - 1
        g = z % 3
        return g
    if wast_num == "NONE" :
        return  fruite[the_num(row , columns_number , column)]
    if len(column_arr) == 0 :
        return fruite[the_num(row , columns_number , column , wast_num)]
    else :
        column_arr.sort()
        start = 0
        end   = len(column_arr) -1
        needed_co = 0
        while (start <= end) :
            middel = math.floor((start + end) / 2)
            if column_arr[middel] > column :
                if middel == 0:
                    needed_co = column
                    break
                if column_arr[middel-1] < column:
                    needed_co= column - len(column_arr[slice(0 , middel )])
                    break
                else:
                    end = middel - 1
            elif column_arr[middel] < column:
                if middel == len(column_arr) - 1:
                    needed_co = column - len(column_arr)
                    break
                if column_arr[middel + 1]> column:
                    needed_co = column  - len(column_arr[slice(0 , middel+1)])
                    break
                else:
                    start = middel + 1
            else:
                needed_co = "Waste"
                break
        if needed_co == 'Waste' :
            return needed_co
        else :
            return fruite[the_num(row , columns_number , needed_co , wast_num)]
for i in range(0 , queries) :
    y = list(map(int , input().split()))
    wast   = find_wast_rows(y[0] , arr)
    column = []
    if wast == y[0] :
        column = arr[indexs[f'{wast}']]['in']
        wast    = arr[indexs[f'{wast}']]['up']
    else :
        if wast == "NONE" :
            wast = 0
        else :
            wast    = arr[indexs[f'{wast}']]['up'] + len(arr[indexs[f'{wast}']]['in'])
    print(calc(wast ,column, y[0] , y[1] , columns ))